package simpledb.index;

import simpledb.common.DbException;
import simpledb.common.Debug;
import simpledb.common.Type;
import simpledb.execution.Predicate;
import simpledb.storage.BufferPool;
import simpledb.storage.Field;
import simpledb.storage.RecordId;
import simpledb.storage.Tuple;
import simpledb.storage.IntField;

import java.io.*;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * BTreeLeafPage 类表示一个 B+ 树索引文件中的叶子页面。
 * 它实现了 Page 接口，供 BufferPool 使用。
 *
 * 每个 BTreeLeafPage 对象包含：
 * - 页面头部信息（header）
 * - 元组数组（tuples）
 * - 插槽数量（numSlots）
 * - 左右兄弟页指针（leftSibling、rightSibling）
 */
public class BTreeLeafPage extends BTreePage {

    private final byte[]  header;      // 头部字节数组，记录插槽是否被使用
    private final Tuple[] tuples;      // 当前页面存储的元组数组
    private final int     numSlots;    // 插槽数量

    private int           leftSibling; // 左兄弟页面编号（页号）
    private int           rightSibling; // 右兄弟页面编号（页号）

    /**
     * 调试用方法：检查当前页面的完整性。
     * 确保数据有序、记录 ID 正确，并满足最小占用率要求。
     */
    public void checkRep(int fieldid, Field lowerBound, Field upperBound, boolean checkoccupancy, int depth) {
        Field prev = lowerBound;
        assert (this.getId().pgcateg() == BTreePageId.LEAF);

        Iterator<Tuple> it = this.iterator();
        while (it.hasNext()) {
            Tuple t = it.next();
            assert (null == prev || prev.compare(Predicate.Op.LESS_THAN_OR_EQ, t.getField(fieldid)));
            prev = t.getField(fieldid);
            assert (t.getRecordId().getPageId().equals(this.getId()));
        }

        assert null == upperBound || null == prev || (prev.compare(Predicate.Op.LESS_THAN_OR_EQ, upperBound));

        assert !checkoccupancy || depth <= 0 || (getNumTuples() >= getMaxTuples() / 2);
    }

    /**
     * 构造函数：从磁盘读取的数据中创建一个 BTreeLeafPage。
     * 数据格式包括：
     * - 父节点指针
     * - 左右兄弟指针
     * - 头部位图（标识插槽是否使用）
     * - 元组数据
     *
     * @param id 页面ID
     * @param data 原始字节数据
     * @param key 字段索引键
     */
    public BTreeLeafPage(BTreePageId id, byte[] data, int key) throws IOException {
        super(id, key);
        this.numSlots = getMaxTuples(); // 初始化最大插槽数
        DataInputStream dis = new DataInputStream(new ByteArrayInputStream(data));

        // 读取父节点和兄弟节点指针
        try {
            Field f = Type.INT_TYPE.parse(dis);
            this.parent = ((IntField) f).getValue();
        } catch (java.text.ParseException e) {
            e.printStackTrace();
        }

        try {
            Field f = Type.INT_TYPE.parse(dis);
            this.leftSibling = ((IntField) f).getValue();
        } catch (java.text.ParseException e) {
            e.printStackTrace();
        }

        try {
            Field f = Type.INT_TYPE.parse(dis);
            this.rightSibling = ((IntField) f).getValue();
        } catch (java.text.ParseException e) {
            e.printStackTrace();
        }

        // 分配并读取页面头部
        header = new byte[getHeaderSize()];
        for (int i = 0; i < header.length; i++)
            header[i] = dis.readByte();

        tuples = new Tuple[numSlots];
        try {
            // 分配并读取页面中的实际元组数据
            for (int i = 0; i < tuples.length; i++)
                tuples[i] = readNextTuple(dis, i);
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }
        dis.close();

        setBeforeImage(); // 设置恢复所需的“之前状态”
    }

    /**
     * 获取该页面可以容纳的最大元组数。
     */
    public int getMaxTuples() {
        int bitsPerTupleIncludingHeader = td.getSize() * 8 + 1;
        int extraBits = 3 * INDEX_SIZE * 8; // 三个指针占用的额外位数
        return (BufferPool.getPageSize() * 8 - extraBits) / bitsPerTupleIncludingHeader;
    }

    /**
     * 计算页面头部所占的字节数。
     */
    private int getHeaderSize() {
        int tuplesPerPage = getMaxTuples();
        int hb = (tuplesPerPage / 8);
        if (hb * 8 < tuplesPerPage)
            hb++;
        return hb;
    }

    /**
     * 返回修改前的页面快照，用于恢复操作。
     */
    public BTreeLeafPage getBeforeImage() {
        try {
            byte[] oldDataRef = null;
            synchronized (oldDataLock) {
                oldDataRef = oldData;
            }
            return new BTreeLeafPage(pid, oldDataRef, keyField);
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1); // 不应发生
        }
        return null;
    }

    /**
     * 设置页面修改前的状态（用于恢复）。
     */
    public void setBeforeImage() {
        synchronized (oldDataLock) {
            oldData = getPageData().clone();
        }
    }

    /**
     * 从输入流中读取下一个元组。
     *
     * @param dis 输入流
     * @param slotId 插槽编号
     * @return 元组对象或 null（如果插槽未使用）
     */
    private Tuple readNextTuple(DataInputStream dis, int slotId) throws NoSuchElementException {
        if (!isSlotUsed(slotId)) {
            // 如果插槽未使用，跳过对应字节数
            for (int i = 0; i < td.getSize(); i++) {
                try {
                    dis.readByte();
                } catch (IOException e) {
                    throw new NoSuchElementException("读取空元组出错");
                }
            }
            return null;
        }

        // 创建新的元组对象
        Tuple t = new Tuple(td);
        RecordId rid = new RecordId(pid, slotId);
        t.setRecordId(rid);
        try {
            for (int j = 0; j < td.numFields(); j++) {
                Field f = td.getFieldType(j).parse(dis);
                t.setField(j, f);
            }
        } catch (java.text.ParseException e) {
            e.printStackTrace();
            throw new NoSuchElementException("解析字段出错！");
        }

        return t;
    }

    /**
     * 将当前页面内容序列化为字节数组，用于写入磁盘。
     * 确保 getPageData() 的输出能被构造函数正确解析。
     *
     * @return 页面对应的字节数组
     */
    public byte[] getPageData() {
        int len = BufferPool.getPageSize();
        ByteArrayOutputStream baos = new ByteArrayOutputStream(len);
        DataOutputStream dos = new DataOutputStream(baos);

        // 写入父节点和兄弟节点指针
        try {
            dos.writeInt(parent);
        } catch (IOException e) {
            e.printStackTrace();
        }
        try {
            dos.writeInt(leftSibling);
        } catch (IOException e) {
            e.printStackTrace();
        }
        try {
            dos.writeInt(rightSibling);
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 写入头部字节
        for (byte b : header) {
            try {
                dos.writeByte(b);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        // 写入所有元组数据
        for (int i = 0; i < tuples.length; i++) {
            if (!isSlotUsed(i)) {
                // 插槽未使用，填充零字节
                for (int j = 0; j < td.getSize(); j++) {
                    try {
                        dos.writeByte(0);
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                continue;
            }

            // 插槽已使用，写入元组字段
            for (int j = 0; j < td.numFields(); j++) {
                Field f = tuples[i].getField(j);
                try {
                    f.serialize(dos);
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

        // 补充空白字节以填满页面大小
        int zerolen = BufferPool.getPageSize() - (header.length + td.getSize() * tuples.length + 3 * INDEX_SIZE);
        byte[] zeroes = new byte[zerolen];
        try {
            dos.write(zeroes, 0, zerolen);
        } catch (IOException e) {
            e.printStackTrace();
        }

        try {
            dos.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }

        return baos.toByteArray();
    }

    /**
     * 删除指定的元组。该元组应被更新以表明它不再存储在任何页面上。
     * @param t 要删除的元组
     * @throws DbException 如果该元组不在当前页面上，或者插槽已经为空
     */
    public void deleteTuple(Tuple t) throws DbException {
        RecordId rid = t.getRecordId();
        if (rid == null)
            throw new DbException("试图删除没有 RecordId 的元组");
        // 检查页号和表号是否匹配
        if ((rid.getPageId().getPageNumber() != pid.getPageNumber())
            || (rid.getPageId().getTableId() != pid.getTableId()))
            throw new DbException("试图删除无效页面或表上的元组");
        // 插槽未使用（即元组不存在）
        if (!isSlotUsed(rid.getTupleNumber()))
            throw new DbException("试图删除空元组");

        // 标记该插槽为未使用
        markSlotUsed(rid.getTupleNumber(), false);
        // 清除元组的记录 ID
        t.setRecordId(null);
    }

    /**
     * 将指定元组插入到页面中，保持所有记录按顺序排列；
     * 插入后，该元组应更新以表明它现在存储在本页面上。
     *
     * @param t 要插入的元组
     * @throws DbException 如果页面已满（无空插槽）或元组描述不匹配
     */
    public void insertTuple(Tuple t) throws DbException {
        // 检查元组描述是否一致
        if (!t.getTupleDesc().equals(td))
            throw new DbException("元组描述不匹配，在插入时发生错误");

        // 找第一个空插槽
        int emptySlot = -1;
        for (int i = 0; i < numSlots; i++) {
            if (!isSlotUsed(i)) {
                emptySlot = i;
                break;
            }
        }

        // 如果没有空插槽则抛出异常
        if (emptySlot == -1)
            throw new DbException("尝试向无空插槽的页面添加元组");

        // 找到最后一个小于等于要插入键值的位置
        int lessOrEqKey = -1;
        Field key = t.getField(keyField); // 获取当前元组的关键字段
        for (int i = 0; i < numSlots; i++) {
            if (isSlotUsed(i)) {
                if (tuples[i].getField(keyField).compare(Predicate.Op.LESS_THAN_OR_EQ, key))
                    lessOrEqKey = i;
                else
                    break;
            }
        }

        // 移动记录，找到合适位置插入新元组，保持排序
        int goodSlot = -1;
        if (emptySlot < lessOrEqKey) {
            for (int i = emptySlot; i < lessOrEqKey; i++) {
                moveRecord(i + 1, i);
            }
            goodSlot = lessOrEqKey;
        } else {
            for (int i = emptySlot; i > lessOrEqKey + 1; i--) {
                moveRecord(i - 1, i);
            }
            goodSlot = lessOrEqKey + 1;
        }

        // 在正确位置插入元组
        markSlotUsed(goodSlot, true);
        Debug.log(1, "BTreeLeafPage.insertTuple: 新元组，表ID = %d 页面ID = %d 插槽ID = %d", pid.getTableId(),
            pid.getPageNumber(), goodSlot);

        // 设置元组的记录 ID 并保存
        RecordId rid = new RecordId(pid, goodSlot);
        t.setRecordId(rid);
        tuples[goodSlot] = t;
    }

    /**
     * 将一个记录从一个插槽移动到另一个插槽，
     * 同时更新对应的头部信息和 RecordId。
     *
     * @param from 原始插槽编号
     * @param to 目标插槽编号
     */
    private void moveRecord(int from, int to) {
        if (!isSlotUsed(to) && isSlotUsed(from)) {
            markSlotUsed(to, true);
            RecordId rid = new RecordId(pid, to);
            tuples[to] = tuples[from];
            tuples[to].setRecordId(rid);
            markSlotUsed(from, false);
        }
    }

    /**
     * 获取当前页面的左兄弟页面的页面 ID。
     * @return 左兄弟页面的 BTreePageId 对象，若不存在则返回 null
     */
    public BTreePageId getLeftSiblingId() {
        if (leftSibling == 0) {
            return null;
        }
        return new BTreePageId(pid.getTableId(), leftSibling, BTreePageId.LEAF);
    }

    /**
     * 获取当前页面的右兄弟页面的页面 ID。
     * @return 右兄弟页面的 BTreePageId 对象，若不存在则返回 null
     */
    public BTreePageId getRightSiblingId() {
        if (rightSibling == 0) {
            return null;
        }
        return new BTreePageId(pid.getTableId(), rightSibling, BTreePageId.LEAF);
    }

    /**
     * 设置当前页面的左兄弟页面 ID。
     * @param id 新的左兄弟页面 ID
     * @throws DbException 如果 ID 不合法（表 ID 不匹配或不是叶子节点）
     */
    public void setLeftSiblingId(BTreePageId id) throws DbException {
        if (id == null) {
            leftSibling = 0;
        } else {
            if (id.getTableId() != pid.getTableId()) {
                throw new DbException("设置左兄弟时表 ID 不匹配");
            }
            if (id.pgcateg() != BTreePageId.LEAF) {
                throw new DbException("左兄弟必须是叶子节点");
            }
            leftSibling = id.getPageNumber();
        }
    }

    /**
     * 设置当前页面的右兄弟页面 ID。
     * @param id 新的右兄弟页面 ID
     * @throws DbException 如果 ID 不合法（表 ID 不匹配或不是叶子节点）
     */
    public void setRightSiblingId(BTreePageId id) throws DbException {
        if (id == null) {
            rightSibling = 0;
        } else {
            if (id.getTableId() != pid.getTableId()) {
                throw new DbException("设置右兄弟时表 ID 不匹配");
            }
            if (id.pgcateg() != BTreePageId.LEAF) {
                throw new DbException("右兄弟必须是叶子节点");
            }
            rightSibling = id.getPageNumber();
        }
    }

    /**
     * 返回当前页面中已使用的元组数量。
     * 即：总插槽数减去空插槽数量。
     */
    public int getNumTuples() {
        return numSlots - getNumEmptySlots();
    }

    /**
     * 返回当前页面中空插槽的数量。
     */
    public int getNumEmptySlots() {
        int cnt = 0;
        for (int i = 0; i < numSlots; i++)
            if (!isSlotUsed(i))
                cnt++;
        return cnt;
    }

    /**
     * 判断指定索引位置的插槽是否被使用。
     * @param i 插槽编号
     * @return 如果该插槽已被占用，返回 true；否则返回 false
     */
    public boolean isSlotUsed(int i) {
        int headerbit = i % 8; // 计算在字节中的位位置（0~7）
        int headerbyte = (i - headerbit) / 8; // 所在的字节位置
        return (header[headerbyte] & (1 << headerbit)) != 0;
    }

    /**
     * 标记指定插槽为已使用或未使用。
     * @param i 插槽编号
     * @param value true 表示标记为已使用，false 表示未使用
     */
    private void markSlotUsed(int i, boolean value) {
        int headerbit = i % 8;
        int headerbyte = (i - headerbit) / 8;

        Debug.log(1, "BTreeLeafPage.setSlot: 设置插槽 %d 为 %b", i, value);
        if (value)
            header[headerbyte] |= 1 << headerbit; // 设置该位为 1
        else
            header[headerbyte] &= (0xFF ^ (1 << headerbit)); // 清除该位为 0
    }

    /**
     * 获取一个迭代器，用于遍历页面中所有元组。
     * 注意：该迭代器不会返回空插槽中的数据。
     * 调用 remove 方法会抛出 UnsupportedOperationException。
     *
     * @return Tuple 类型的迭代器
     */
    public Iterator<Tuple> iterator() {
        return new BTreeLeafPageIterator(this);
    }

    /**
     * 获取一个逆序迭代器，用于从后往前遍历页面中的所有元组。
     * 注意：该迭代器不会返回空插槽中的数据。
     * 调用 remove 方法会抛出 UnsupportedOperationException。
     *
     * @return Tuple 类型的逆序迭代器
     */
    public Iterator<Tuple> reverseIterator() {
        return new BTreeLeafPageReverseIterator(this);
    }

    /**
     * 受保护方法，供迭代器获取指定索引位置的元组。
     * @param i 元组索引
     * @return 指定索引的元组
     * @throws NoSuchElementException 如果索引超出范围或插槽为空
     */
    Tuple getTuple(int i) throws NoSuchElementException {

        if (i >= tuples.length)
            throw new NoSuchElementException();

        try {
            if (!isSlotUsed(i)) {
                Debug.log(1, "BTreeLeafPage.getTuple: 插槽 %d 在 %d:%d 上未使用", i, pid.getTableId(), pid.getPageNumber());
                return null;
            }

            Debug.log(1, "BTreeLeafPage.getTuple: 返回第 %d 个元组", i);
            return tuples[i];

        } catch (ArrayIndexOutOfBoundsException e) {
            throw new NoSuchElementException();
        }
    }

    /**
     * 辅助类，实现针对 BTreeLeafPage 的 Java 迭代器功能。
     * 支持顺序访问页面上的所有非空元组。
     */
    class BTreeLeafPageIterator implements Iterator<Tuple> {
        int                 curTuple     = 0;   // 当前尝试读取的元组索引
        Tuple               nextToReturn = null; // 下一个要返回的元组
        final BTreeLeafPage p;                  // 当前页面引用

        public BTreeLeafPageIterator(BTreeLeafPage p) {
            this.p = p;
        }

        /**
         * 是否还有下一个可用的元组。
         */
        public boolean hasNext() {
            if (nextToReturn != null)
                return true;

            try {
                while (true) {
                    nextToReturn = p.getTuple(curTuple++);
                    if (nextToReturn != null)
                        return true;
                }
            } catch (NoSuchElementException e) {
                return false;
            }
        }

        /**
         * 返回下一个可用的元组。
         */
        public Tuple next() {
            Tuple next = nextToReturn;

            if (next == null) {
                if (hasNext()) {
                    next = nextToReturn;
                    nextToReturn = null;
                    return next;
                } else
                    throw new NoSuchElementException();
            } else {
                nextToReturn = null;
                return next;
            }
        }

        /**
         * 不支持移除操作。
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    /**
     * 辅助类，实现针对 BTreeLeafPage 的逆序 Java 迭代器功能。
     * 支持从后往前访问页面上的所有非空元组。
     */
    class BTreeLeafPageReverseIterator implements Iterator<Tuple> {
        int                 curTuple;           // 当前尝试读取的元组索引（从最大开始递减）
        Tuple               nextToReturn = null; // 下一个要返回的元组
        final BTreeLeafPage p;                  // 当前页面引用

        public BTreeLeafPageReverseIterator(BTreeLeafPage p) {
            this.p = p;
            this.curTuple = p.getMaxTuples() - 1; // 初始化为最后一个可能的元组索引
        }

        /**
         * 是否还有上一个可用的元组。
         */
        public boolean hasNext() {
            if (nextToReturn != null)
                return true;

            try {
                while (curTuple >= 0) {
                    nextToReturn = p.getTuple(curTuple--);
                    if (nextToReturn != null)
                        return true;
                }
                return false;
            } catch (NoSuchElementException e) {
                return false;
            }
        }

        /**
         * 返回上一个可用的元组。
         */
        public Tuple next() {
            Tuple next = nextToReturn;

            if (next == null) {
                if (hasNext()) {
                    next = nextToReturn;
                    nextToReturn = null;
                    return next;
                } else
                    throw new NoSuchElementException();
            } else {
                nextToReturn = null;
                return next;
            }
        }

        /**
         * 不支持移除操作。
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}
